package com.example.leetcode.prcatice;

/**
 * 一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
 *
 * 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。
 * 给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sum-of-beauty-of-all-substrings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1781 {



    public int beautySum(String s) {
        int r = 0;
        for (int i = 0;i<s.length();i++) {
            int[] cnt = new int[26];
            int max = 0;
            for (int j = i;j<s.length();j++) {
                cnt[s.charAt(j) - 'a']++;
                max = Math.max(cnt[s.charAt(j) - 'a'],max);
                int min = Integer.MAX_VALUE;
                for (int k = 0;k<26;k++) {
                    if (cnt[k] > 0) {
                        min = Math.min(min,cnt[k]);
                    }
                }
                r = r + max - min;
            }
        }
        return r;
    }
}
